package internal.radix;

import java.util.Arrays;

/**
 * @描述：基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而这种排序方法必须是稳定的
 * @作者：hongxingfan
 * @时间：2014年9月5日 下午4:42:28
 */
public class RadixSort {

	public static void main(String[] args) {
		// int[] datas = { 19, 4, 1, 8, 7, 52, 2, 45, 30, 4, 6 };
		int[] datas = { 19, 9, 21, 6 };
		radixSort(datas, 10, 2); // 10代表区余%10,2代表最大数字的位数1000->3还是100->2还是10->1

		System.out.println(Arrays.toString(datas));
	}

	// 在基数排序中可以引入高位优先和地位优先排序的算法
	public static void radixSort(int[] datas, int radix, int d) {
		int length = datas.length;
		int[] tmp = new int[length];
		int[] bucket = new int[radix];
		// 此处的for循环就是每一步取余，以下的作用就是桶排序的内容了。因子变量是余数和数字位数
		for (int i = 0, rate = 1; i < d; i++) {
			Arrays.fill(bucket, 0);
			System.arraycopy(datas, 0, tmp, 0, length);
			// 用到桶排序
			for (int j = 0; j < length; j++) {
				int subKey = (tmp[j] / rate) % radix;
				bucket[subKey]++;
			}
			for (int j = 1; j < radix; j++) {
				bucket[j] = bucket[j] + bucket[j - 1];
			}
			// 基数在桶中的位置
			for (int m = length - 1; m >= 0; m--) {
				int subKey = (tmp[m] / rate) % radix;
				datas[--bucket[subKey]] = tmp[m]; // --bucket的作用就是处理同一个桶中的数字
			}
			rate *= radix;
		}
	}

}
